package algorithm.t202111;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/7 10:13
 * @description :5道
 * 初雪，立冬，在今天同时来临，最后一个冬天。夜晚的漫天雪花，凌晨中激动的喊叫声在告知LOLS11的冠军是中国战队，同学们喊着：EDG牛逼，EDG牛逼... 声音
 * 弥漫在整个校园，一切仿佛似乎一刹那就回到了三年的那个晚上，同样是中国战队冠军，只不过那一年，是2018年。
 * 时间太快太快，我还有太多太多想看的事，还有太多想说的话，一切难以言表的心情此时在心中涌动。
 * persevere to last
 * 2021.11.07
 * 2021年11月7日19:27:36
 */
public class t20211107 {


    //598.范围求和2
    public int maxCount(int m, int n, int[][] ops) {

        for (int[] op : ops) {
            m = Math.min(m, op[0]);
            n = Math.min(n, op[1]);
        }
        return m * n;
    }

    //91.解码方法
    public int numDecodings2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int len = s.length();
        s = " " + s;
        char[] chars = s.toCharArray();

        int[] dp = new int[len + 1];//dp[i]表示前i个字符能够形成的的编码数
        dp[0] = 1;

        for (int i = 1; i <= len; i++) {

            // a : 代表「当前位置」单独形成 item
            int a = chars[i] - '0', b = (chars[i - 1] - '0') * 10 + (chars[i] - '0');
            // b : 代表「当前位置」与「前一位置」共同形成 item

            //看看a是否满足
            if (a >= 1 && a <= 9) {
                dp[i] = dp[i - 1];
            }

            // 如果 b 属于有效值，那么 f[i] 可以由 f[i - 2] 或者 f[i - 1] & f[i - 2] 转移过来
            if (b >= 10 && b <= 26) {
                dp[i] += dp[i - 2];
            }

        }
        return dp[len];
    }

    public int numDecodings(String s) {
        int n = s.length();
        s = " " + s;
        char[] cs = s.toCharArray();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            // a : 代表「当前位置」单独形成 item
            // b : 代表「当前位置」与「前一位置」共同形成 item
            int a = cs[i] - '0', b = (cs[i - 1] - '0') * 10 + (cs[i] - '0');
            // 如果 a 属于有效值，那么 f[i] 可以由 f[i - 1] 转移过来
            if (1 <= a && a <= 9) f[i] = f[i - 1];
            // 如果 b 属于有效值，那么 f[i] 可以由 f[i - 2] 或者 f[i - 1] & f[i - 2] 转移过来
            if (10 <= b && b <= 26) f[i] += f[i - 2];
        }
        return f[n];
    }

    //139.单词拆分
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;

        for (int i = 0; i < len; i++) {
            if (!dp[i]) {
                continue;
            }

            for (String word : wordDict) {
                if (word.length() + i <= s.length() && s.startsWith(word, i)) {
                    dp[word.length() + i] = true;
                }

            }

        }

        return dp[len];
    }

    //面试题16.07 最大数值
    public int maximum(int a, int b) {

        //获取差值符号
        int k = b - a >>> 31;

        //获取a的符号和b的符号
        int a_sign = a >>> 31, b_sign = b >>> 31;

        //看看两者是否异号
        int diff = a_sign ^ b_sign;

        //若diff为1，说明两者异号，此时不需要比较大小，为+号的那个数肯定大。
        //若diff为0，则说明两者同号（可能都为-，也可能都为+），此时根据k来判断
        k = k & (diff ^ 1) | b_sign & diff;
        return a * k + b * (k ^ 1);
    }

    String[] num2str_samll = {
            "Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven",
            "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"
    };
    String[] num2str_medium = {
            "", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"
    };
    String[] num2str_large = {"Billion", "Million", "Thousand", ""};

    //面试题16.08 整数的英语表示
    public String numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        }
        StringBuffer buffer = new StringBuffer();

        for (int i = (int) 1e9, j = 0; i >= 1; i /= 1000, j++) {
            if (num < i) continue;
            buffer.append(num2Str(num / i) + num2str_large[j] + " ");
            num %= i;
        }

        while (buffer.charAt(buffer.length() - 1) == ' ') buffer.deleteCharAt(buffer.length() - 1);

        return buffer.toString();
    }

    private String num2Str(int num) {
        String ans = "";

        if (num >= 100) {
            ans += num2str_samll[num / 100] + " Hundred ";
            num %= 100;
        }

        if (num >= 20) {
            ans += num2str_medium[num / 10] + " ";
            num %= 10;
        }
        if (num != 0) {
            ans += num2str_samll[num] + "  ";
        }

        return ans;
    }


    public static void main(String[] args) {
        t20211107 t20211107 = new t20211107();
        System.out.println(t20211107.numberToWords(123));

    }

}

